import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.lang.Object;


@SuppressWarnings("hiding")
public class BinaryHeap<Object extends Comparable<Object>> implements Queue<Object> {
	private static final int DEFAULT_CAPACITY = 64;
	private static final int CAPACITY_STEP = 32;
	
	private Object[] heap;
	private  int occupancy = 0;
	
	/**
	 * Constructor sets initial capacity to a default value
	 * @param c
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public BinaryHeap(Class<Object> cs, int initialCapacity){
		heap = (Object[])  Array.newInstance(cs, initialCapacity);
		
	}
	
	public BinaryHeap(Class<Object> cs){
		this(cs,DEFAULT_CAPACITY);
	}



	public void clear() {
		for(int i=0;i<occupancy;i++)
			heap[i] = null;
		
	}

	public boolean contains(Object o) {
		try{
			indexOf(o);
			return true;
		}catch(NoSuchElementException e){
			return false;
		}
		
	}
	private int indexOf(Object o){
		for(int i=0;i<occupancy;i++){
			if(o==null? heap[i]==null:o.equals(heap[i]))
				return i;
		}
		throw new NoSuchElementException();
	}

	public boolean containsAll(Collection<?> c) {
		for(java.lang.Object f:c){
			if(!contains(f))
				return false;
		}
		return true;
	}


	public boolean isEmpty() {
		return occupancy==0;
	}
	/**
	 * Retrieves, but does not remove the highest priority element in the queue
	 * @return the head of the queue
	 */
	public Object peek(){
		if (occupancy>0){
			return heap[0];
		}else
			throw new NoSuchElementException();
	}
	/**
	 * Retrieves and remove the highest priority element in the queue
	 * @return the head of the queue
	 */
	public boolean remove(Object o) {
		try{
			int index = indexOf(o);
			heap[index] = heap[--occupancy];
			heap[occupancy] = null;
			if(occupancy>0) pushDown(index);
			return true;
		}catch(NoSuchElementException e){
			return false;
		}
	}

	private void pushDown(int index) {
		Object e = heap[index];
		boolean push;
		int leftIndex,rightIndex, swapIndex;
		do{
			push = false;
			/*If the left or right children are empty, just use the current node for simplicity
			 * of comparision as it will never have higher priority than itself
			 */
			leftIndex = (left(index)< occupancy)? left(index):index;
			rightIndex = (right(index)<occupancy) ?right(index): index;
			
			//If either child has higher priority then current node
			if(e.compareTo(heap[leftIndex])>0 ||e.compareTo(heap[rightIndex])>0){
				push = true;
				
				//... swap the current node with the highest priority child
				swapIndex = heap[leftIndex].compareTo(heap[rightIndex])<0 ? leftIndex: rightIndex;
				heap[index] = heap[swapIndex];
				heap[swapIndex] = e;
				index = swapIndex;
			}
		}while(push && index<occupancy-1);
		
	}

	private int left(int index){
		return index*2;
	}
	
	private int right(int index){
		return index*2+1;
	}
	
	public boolean removeAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}


	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}


	public int size() {
		return occupancy;
	}


	public Object[] toArray() {
		throw new UnsupportedOperationException();
	}

	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException();
	}







	public boolean addAll(Collection<? extends Object> c) {
		if(c.size() ==0)
			return false;
		/* if the current capacity will not contain all elements to be added, 
		 * pre-emptively expand it
		 */
		if(occupancy+c.size() >=heap.length){
			int newCapacity = heap.length + c.size() + CAPACITY_STEP;
			heap = Arrays.copyOf(heap,newCapacity);
		}
		for(Object e:c)
			add(e);
		return true;
	}

	/**
	 * Inserts the specified element into the queue according to its natural order
	 * @param e the element to add
	 * @return: true
	 */
	public boolean add(Object e) {
		if(occupancy >= heap.length){
			heap = Arrays.copyOf(heap,heap.length+CAPACITY_STEP);
		}
		//Insert the new element at the first available leaft of the HEAP.
		int index = occupancy++;
		heap[index] = e;
		int parentIndex = parent(index);
		
		//propagate the new element up the heap until its parent has higher priority
		while(index>1 && heap[parentIndex].compareTo(e)>0){
			heap[index] = heap[parentIndex];
			heap[parentIndex] = e;
			index = parentIndex;
			parentIndex = parent(index);
		}
		return true;
	}
	private int parent(int index){
		return (--index)/2;
	}
	
	public boolean offer(Object e) {
		if(occupancy>=heap.length){
			return false;
		}else{
			add(e);
			return true;
		}
	}




	public Iterator<Object> iterator() {
		throw new UnsupportedOperationException();
	}


	public Object element() {
		return peek();
	}


	public Object poll() {
		
		return remove();
	}

	/**
	 * Retrieves and remove the highest priority element in teh queue
	 * @return the head of the queue
	 */
	public Object remove() {
		if(occupancy==0)
			return null;
		Object e = heap[0];
		heap[0] = heap[--occupancy];
		heap[occupancy] =null;
		if(occupancy>0) pushDown(0);
		return e;
	}


	public boolean contains(java.lang.Object o) {
		
		return contains(o);
	}

	public boolean remove(java.lang.Object o) {
		
		return remove(o);
	}



}
